package br.uece.comp.paa.entity;

import java.util.LinkedList;
import java.util.List;

import br.uece.comp.paa.entity.beb.ArestaBB;
import br.uece.comp.paa.entity.grafo.Aresta;
import br.uece.comp.paa.entity.grafo.Grafo;
import br.uece.comp.paa.entity.param.Solucao;
import br.uece.comp.paa.util.GeradorCombinacao;

public abstract class Varredura extends GeradorArvoreMinima {

	protected GeradorCombinacao gerador;

	private ArestaBB[] arestas;

	private int qtdVertices;

	private static final int GRUPO_A = 0;

	private static final int GRUPO_B = 1;// 30.260.340

	protected boolean continuar = true;

	public Varredura(Grafo g) {
		super(g);
		qtdVertices = g.getVertices().length;
	}

	protected void inicializarAtributos(Grafo g) {
		gerarArestasBB(g);
		gerador = new GeradorCombinacao(arestas.length, qtdVertices - 1);
	}

	private void gerarArestasBB(Grafo g) {
		arestas = new ArestaBB[((qtdVertices * qtdVertices) - qtdVertices) / 2];
		Double[][] matrizCusto = g.getMatrizCusto();
		int count = 0;

		for (int i = 0; i < qtdVertices; i++) {
			for (int j = i + 1; j < qtdVertices; j++) {
				arestas[count] = new ArestaBB(count, i, j, matrizCusto[i][j]);
				count++;
			}
		}
	}

	/**
	 * Avalia se uma solução é viável e retorna o custo dela. Se a solução não
	 * for viável, retorna null.
	 * 
	 * @param solucao
	 */
	protected Double avaliar(int grauMaximo, Solucao solucao) {
		Double custo = null;
		int idAresta;

		if (ehViavel(grauMaximo, solucao)) {
			custo = 0d;
			solucao.reset();

			while (solucao.hasNext()) {
				idAresta = solucao.getNextAresta();
				custo += arestas[idAresta].getCusto();
			}
			solucao.setCusto(custo);
		}

		return custo;
	}

	protected Double avaliar(int grauMaximo, int[] solucao, int tam,
			Double custoInicial) {
		Double custo = null;

		if (ehViavel(grauMaximo, solucao, tam)) {

			custo = custoInicial + arestas[solucao[tam]].getCusto();

		}

		return custo;
	}

	protected boolean ehViavel(int grauMaximo, Solucao solucao) {
		int[] grau = new int[qtdVertices];
		int[] grupo = new int[qtdVertices];
		int v1, v2;
		v1 = 0;
		Double matrizCusto[][] = new Double[qtdVertices][qtdVertices];

		int idAresta;
		solucao.reset();

		while (solucao.hasNext()) {
			idAresta = solucao.getNextAresta();
			v1 = arestas[idAresta].getVertice1();
			v2 = arestas[idAresta].getVertice2();

			grau[v1]++;
			grau[v2]++;

			matrizCusto[v1][v2] = arestas[idAresta].getCusto();
			matrizCusto[v2][v1] = arestas[idAresta].getCusto();
		}

		for (int g : grau) {
			if (g > grauMaximo || g < 1) {
				return false;
			}
		}

		marcarNovoGrupo(grupo, v1, matrizCusto);

		if (temCiclo(grupo)) {
			return false;
		}

		return true;
	}

	protected boolean ehViavel(int grauMaximo, int[] solucao, int tam) {
		int[] grau = new int[qtdVertices];
		int[] grupo = new int[qtdVertices];
		int v1, v2;
		v1 = 0;
		Double matrizCusto[][] = new Double[qtdVertices][qtdVertices];

		int idAresta;

		for (int i = 0; i <= tam; i++) {
			idAresta = solucao[i];

			v1 = arestas[idAresta].getVertice1();
			v2 = arestas[idAresta].getVertice2();

			grau[v1]++;
			grau[v2]++;

			matrizCusto[v1][v2] = arestas[idAresta].getCusto();
			matrizCusto[v2][v1] = arestas[idAresta].getCusto();
		}

		for (int g : grau) {
			if (g > grauMaximo) {
				return false;
			}
		}

		if (temCiclo(grupo, grau, matrizCusto)) {
			return false;
		}

		return true;
	}

	private boolean temCiclo(int[] grupo) {
		for (int g : grupo) {
			if (g == GRUPO_A) {
				return true;
			}
		}
		return false;
	}

	private boolean temCiclo(int[] grupo, int[] grau, Double[][] matrizCustoAgm) {
		List<Boolean> results = new LinkedList<Boolean>();
		
		for(int i = 0; i< grau.length; i++) {
			if(grau[i] > 0) {
				for(int g = 0; g < grupo.length; g++) {
					grupo[g] = GRUPO_A;
				}
				temCicloVertice(grupo, i, matrizCustoAgm, results);

				while(results.size() > 0) {
					if(results.remove(0)) {
						return true;
					}
				}
			}
		}
		return false;
	}
	private void temCicloVertice(int[] grupo, int v, Double[][] matrizCustoAgm, List<Boolean> lista) {

		if (grupo[v] != GRUPO_B) {
			grupo[v] = GRUPO_B;
			for (int i = v+1; i < matrizCustoAgm[v].length; i++) {
				if (matrizCustoAgm[v][i] != null) {
					temCicloVertice(grupo, i, matrizCustoAgm, lista);
				}
			}
		} else {
			lista.add(true);
		}

		lista.add(false);
	}

	private void marcarNovoGrupo(int[] grupo, int v, Double[][] matrizCustoAgm) {
		if (grupo[v] != GRUPO_B) {
			grupo[v] = GRUPO_B;
			for (int i = 0; i < matrizCustoAgm[v].length; i++) {
				if (matrizCustoAgm[v][i] != null) {
					marcarNovoGrupo(grupo, i, matrizCustoAgm);
				}
			}
		}
	}

	public List<Aresta> obterListaArestas(Solucao solucao) {
		List<Aresta> arestasSolucao = new LinkedList<Aresta>();
		solucao.reset();

		while (solucao.hasNext()) {
			arestasSolucao.add(arestas[solucao.getNextAresta()]);
		}

		return arestasSolucao;
	}

	public void parar() {
		continuar = false;
		
	}
}
